In a large-scale distributed storage system, garbage collectors use garbage collection policies to determine whether objects in the distributed storage system should be removed. For example, a garbage collection policy may specify that objects that are older than M days and that have not been accessed for the past N days should be deleted. The value of M and N is selected so that there is a balance between retaining objects that are still being accessed (or required) by clients and freeing up storage space occupied by unneeded data. The age (or the last access time) of an object is typically determined by saving a creation timestamp corresponding to the time at which the object was created (or a last-access timestamp corresponding to the time at which the last access of the object occurred) and calculating the difference between the current time and the creation timestamp (or the last-access timestamp). This technique works reasonably well if the clock is reliable (i.e., the clock is accurate and the clock skews are bounded in a small range) and if no critical actions (e.g., deleting objects) are taken based on the age of the object. However, if the clock is unreliable (e.g., the clock has large clock skews or is unreliable such that the clock either advances forward in time, backwards in time, or does not advance in time), the calculation of the age (or the last access time) of an object may result in objects being prematurely deleted. Thus, it is desirable to determine the age (or the last access time) of an object in the presence of unreliable clocks.